The strategy for locating and sampling possible fossilized Martian organisms benefits from our experience with fossil microbial ecosystems on Earth. Evidence of early life is typically preserved as stromatolites in carbonates and cherts, and as microfossils in cherts, carbonates and shales. Stromatolites, which are laminated flat or domal structures built by microbial communities, are very likely the oldest and most widespread relics of early life. These communities flourished in supratidal to subtidal coastal benthic environments, wherever sunlight was available and where incoming sediments were insufficient to bury the communities before they became established. A logical site for such communities on Mars might be those areas in an ancient lake bed which were furthest from sediment input, but were still sufficiently shallow to have received sunlight. Therefore, although some sites within Valles Marineris might have contained ponded water, the possibly abundant sediment inputs might have overwhelmed stromatolite-like communities. Localized depressions which acted as catchment basins for ancient branched valley systems might be superior sites. Perhaps such depressions received drainage which, because of the relatively modest water discharges implied for these streams, was relatively low in transported sediment. Multiple streams converging on a single basin might have been able to maintain a shallow water environment for extended periods of time.